package unionFound;
/**
 * 
 * @Title: CandyUnionFindImpl_v1.java 
 * @Package unionFound 
 * @Description: 并查集：QuickUnionFind
 *                  isConnected()方法是时间复杂度是O(1)级别的
 *                  unionElements(p, q)时间复杂度是O(n)级别的
 * @author CandyWall   
 * @date 2021年1月11日 上午11:32:18 
 * @version V1.0
 */
public class CandyUnionFindImpl_v1 implements CandyUnionFind {
    private int[] ids;
    public CandyUnionFindImpl_v1(int size) {
        ids = new int[size];
        for(int i = 0; i < ids.length; i++) {
            ids[i] = i;
        }
    }

    @Override
    // 查看元素p和元素q是否所属同一个集合
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
    
    // 查找索引为index的元素对应的集合编号
    private int find(int index) {
        checkArrayIndexRange(index);
        return ids[index];
    }
    
    /**
     * 校验待操作的数组下标是否合法
     */
    private void checkArrayIndexRange(int index) {
        if(index >= ids.length || index < 0) {
            throw new IllegalArgumentException("索引index不合法！");
        }
    }

    @Override
    // 合并元素p和元素q所属的集合
    public void unionElements(int p, int q) {
        int pid = find(p);
        int qid = find(q);
        if(pid == qid) {
            return;
        }
        for(int i = 0; i < ids.length; i++) {
            if(ids[i] == pid) {
                ids[i] = qid;
            }
        }
    }

    @Override
    public int getSize() {
        return ids.length;
    }

}
